package class20;

// 测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/
public class Code01_PalindromeSubsequence {

	/**
	 * 计算字符串中最长回文子序列的长度（方法1：暴力递归）
	 * 
	 * @param s 输入字符串
	 * @return 最长回文子序列的长度
	 */
	public static int lpsl1(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		// 调用递归函数计算str[0...len-1]范围内的最长回文子序列长度
		return f(str, 0, str.length - 1);
	}

	/**
	 * 递归计算str[L..R]范围内最长回文子序列长度
	 * 
	 * 回文子序列的特点是正读和反读都相同，不要求连续
	 * 
	 * @param str 字符数组
	 * @param L 左边界
	 * @param R 右边界
	 * @return 最长回文子序列长度
	 */
	public static int f(char[] str, int L, int R) {
		// 基础情况1：只有一个字符，回文子序列长度为1
		if (L == R) {
			return 1;
		}
		
		// 基础情况2：只有两个字符
		if (L == R - 1) {
			// 如果两个字符相同，回文子序列长度为2；否则为1
			return str[L] == str[R] ? 2 : 1;
		}
		
		// 普通情况：有多个字符
		// 情况1：不考虑首尾字符，计算str[L+1...R-1]范围内的最长回文子序列长度
		int p1 = f(str, L + 1, R - 1);
		
		// 情况2：不考虑尾字符，计算str[L...R-1]范围内的最长回文子序列长度
		int p2 = f(str, L, R - 1);
		
		// 情况3：不考虑首字符，计算str[L+1...R]范围内的最长回文子序列长度
		int p3 = f(str, L + 1, R);
		
		// 情况4：如果首尾字符相同，那么首尾字符可以作为回文的一部分
		// 此时最长回文子序列长度为首尾两个字符(2)加上str[L+1...R-1]范围内的最长回文子序列长度
		// 如果首尾字符不同，则这种情况不成立，长度为0
		int p4 = str[L] != str[R] ? 0 : (2 + f(str, L + 1, R - 1));
		
		// 返回四种情况中的最大值
		return Math.max(Math.max(p1, p2), Math.max(p3, p4));
	}

	/**
	 * 计算字符串中最长回文子序列的长度（方法2：动态规划）
	 * 
	 * @param s 输入字符串
	 * @return 最长回文子序列的长度
	 */
	public static int lpsl2(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		
		// dp[i][j]表示str[i...j]范围内的最长回文子序列长度
		int[][] dp = new int[N][N];
		
		// 初始化：对角线上的元素（单个字符）回文长度为1
		dp[N - 1][N - 1] = 1;
		for (int i = 0; i < N - 1; i++) {
			dp[i][i] = 1;
			// 相邻两个字符的情况
			dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
		}
		
		// 填充dp表：从下往上，从左往右
		// L从倒数第3行开始向上
		for (int L = N - 3; L >= 0; L--) {
			// R从L+2开始向右（保证区间内至少有3个字符）
			for (int R = L + 2; R < N; R++) {
				// 不考虑首字符或尾字符的情况中取较大值
				dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
				
				// 如果首尾字符相同，可以考虑首尾字符+中间部分的回文长度
				if (str[L] == str[R]) {
					dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
				}
			}
		}
		
		// 返回整个字符串范围内的最长回文子序列长度
		return dp[0][N - 1];
	}

	/**
	 * 计算字符串中最长回文子序列的长度（方法3：转换为最长公共子序列问题）
	 * 
	 * 核心思想：一个字符串的最长回文子序列，等于该字符串与其反转字符串的最长公共子序列
	 * 
	 * @param s 输入字符串
	 * @return 最长回文子序列的长度
	 */
	public static int longestPalindromeSubseq1(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		if (s.length() == 1) {
			return 1;
		}
		
		char[] str = s.toCharArray();
		// 将字符串反转
		char[] reverse = reverse(str);
		// 计算原字符串与反转字符串的最长公共子序列长度
		return longestCommonSubsequence(str, reverse);
	}

	/**
	 * 反转字符数组
	 * 
	 * @param str 原字符数组
	 * @return 反转后的字符数组
	 */
	public static char[] reverse(char[] str) {
		int N = str.length;
		char[] reverse = new char[str.length];
		for (int i = 0; i < str.length; i++) {
			// 从原数组末尾开始取字符，放入新数组开头
			reverse[--N] = str[i];
		}
		return reverse;
	}

	/**
	 * 计算两个字符数组的最长公共子序列长度
	 * 
	 * @param str1 字符数组1
	 * @param str2 字符数组2
	 * @return 最长公共子序列长度
	 */
	public static int longestCommonSubsequence(char[] str1, char[] str2) {
		int N = str1.length;
		int M = str2.length;
		
		// dp[i][j]表示str1[0...i]和str2[0...j]的最长公共子序列长度
		int[][] dp = new int[N][M];
		
		// 初始化左上角
		dp[0][0] = str1[0] == str2[0] ? 1 : 0;
		
		// 初始化第一列
		for (int i = 1; i < N; i++) {
			dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
		}
		
		// 初始化第一行
		for (int j = 1; j < M; j++) {
			dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
		}
		
		// 填充dp表
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < M; j++) {
				// 不考虑str1[i]或str2[j]的情况中取较大值
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				
				// 如果当前字符相同，可以考虑公共子序列长度加1
				if (str1[i] == str2[j]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
			}
		}
		
		// 返回整个范围内的最长公共子序列长度
		return dp[N - 1][M - 1];
	}

	/**
	 * 计算字符串中最长回文子序列的长度（方法4：动态规划优化版）
	 * 
	 * @param s 输入字符串
	 * @return 最长回文子序列的长度
	 */
	public static int longestPalindromeSubseq2(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		if (s.length() == 1) {
			return 1;
		}
		
		char[] str = s.toCharArray();
		int N = str.length;
		
		// dp[i][j]表示str[i...j]范围内的最长回文子序列长度
		int[][] dp = new int[N][N];
		
		// 初始化：对角线上的元素（单个字符）回文长度为1
		dp[N - 1][N - 1] = 1;
		for (int i = 0; i < N - 1; i++) {
			dp[i][i] = 1;
			// 相邻两个字符的情况
			dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
		}
		
		// 填充dp表：从下往上，从左往右
		for (int i = N - 3; i >= 0; i--) {
			for (int j = i + 2; j < N; j++) {
				// 不考虑首字符或尾字符的情况中取较大值
				dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
				
				// 如果首尾字符相同，可以考虑首尾字符+中间部分的回文长度
				if (str[i] == str[j]) {
					dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
				}
			}
		}
		
		// 返回整个字符串范围内的最长回文子序列长度
		return dp[0][N - 1];
	}

}